/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils
{
	public class BTnode
	{
		//二叉树 Binary tree
		
		//data of the Binary-tree node
		private var data:*;
		
		//左孩子和右孩子结点， left child node and right child node being referenced
		private var left:BTnode, right:BTnode;
		
		public function BTnode(initData:*, leftChild:BTnode = null, rightNode:BTnode = null)
		{
			data = initData;
			left = leftChild;
			right = rightChild;
		}
		
		public function get nodeData():*
		{
			return data;
		}
		
		public function get leftChild():BTnode
		{
			return left;
		}
		
		public function get rightChild():BTnode
		{
			return right;
		}
		
		//返回最左边结点的数值， get the most left node's data
		public function get leftMostData():*
		{
			if(left == null)
				return data;
			else 
				return left.leftMostData;
		}
		
		//返回最右边结点的数值， get the most right node's data
		public function get rightMostData():*
		{
			if(right == null)
				return data;
			else
				return right.rightMostData;
		}
		
		//返回树的结点数量， get the total number of the binary tree
		public static function getSize(root:BTnode):uint
		{
			if(root == null)
				return 0;
			else
				return 1 + getSize(root.leftChild) + getSize(root.rightChild);
		}
		
		public function set nodeData(newData:*):void
		{
			data = newData;
		}
		
		public function set leftChild(newBTnode:BTnode):void
		{
			left = newBTnode;
		}
		
		public function set rightChild(newBTnode:BTnode):void
		{
			right = newBTnode;
		}
		
		//中序处理所有结点
		public function inorderPrint(process:Function):void
		{
			if(left != null)
				left.inorderPrint(process);
			process(this);
			if(right != null)
				right.inorderPrint(process);
		}
		
		//后序处理所有结点
		public function postorderPrint(process:Function):void
		{
			if(left != null)
				left.postorderPrint(process);			
			if(right != null)
				right.postorderPrint(process);
			process(this);
		}
		
		//前序处理所有结点
		public function preorderPrint(process:Function):void
		{
			process(this);
			if(left != null)
				left.preorderPrint(process);			
			if(right != null)
				right.preorderPrint(process);		
		}
		
		//判断某结点是否是叶子结点， check if the node if a leaf
		public function isLeaf():Boolean
		{
			return (left == null)&&(right == null);
		}
		
		//打印输出所有结点， print all the node exit
		public function print(depth:uint):void
		{
			var i:uint;
			var space:String = " ";
			for(i = 0; i <= depth; i++)
				space += " ";
			trace(space + data);
			
			if(left != null)
				left.print(depth + 1);
			else if(right != null)
			{
				space = " ";
				for(i = 0; i <= depth + 1; i++)
					space += " ";
				trace(space + "--");
			}
			
			if(right != null)
				right.print(depth + 1);
			else if(left != null)
			{
				space = " ";
				for(i = 0; i <= depth + 1; i++)
					space += " ";
				trace(space + "--");
			}
		}
		
		//删除最左边的结点， remove the most laft node
		public function removeLeftMost():BTnode
		{
			if(left == null)
				return right;
			else
			{
				left = left.removeLeftMost();
				return this;
			}
		}
		
		//删除最右边的结点， remove the most right node
		public function removeRightMost():BTnode
		{
			if(right == null)
				return left;
			else
			{
				right = right.removeRightMost();
				return this;
			}
		}
		
		//返回对二叉树的信息， write a string representing to the binary tree node
		public function toString():String
		{
			return "[BTnode, size=" + getSize(this) + "]";
		}
	}
}